/*
 * @lc app=leetcode.cn id=310 lang=cpp
 *
 * [310] 最小高度树
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    void findLongestPath(int from, vector<int> &path, const vector<vector<int>> &adj, vector<int> &dist)
    {
        path.push_back(from);

        if (from == 0)
        {
            return;
        }
        int curr_dist = dist[from];
        dist[from] = -1;

        for (auto to : adj[from])
        {
            if (dist[to] == curr_dist - 1)
            {
                findLongestPath(to, path, adj, dist);
                return;
            }
        }
    }

    vector<int> distance(int from, const vector<vector<int>> &adj)
    {
        vector<bool> visited(adj.size(), false);
        vector<int> dist(adj.size(), 0); //保存的是节点0到所有节点的距离
        queue<int> q;
        q.push(from);
        visited[from] = true;

        while (!q.empty())
        {
            int i = q.front();
            q.pop();

            for (auto j : adj[i])
            {
                if (!visited[j])
                {
                    dist[j] = dist[i] + 1;
                    visited[j] = true;
                    q.push(j);
                }
            }
        }
        return dist;
    }

    vector<int> findMinHeightTrees(int n, vector<vector<int>> &edges)
    {
        vector<vector<int>> adj(n);
        for (auto &e : edges)
        {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
        }

        vector<int> dist = distance(0, adj); //计算 0 到 任意节点的距离

        vector<int> ans;

        vector<int> longest_path;
        int from = max_element(dist.begin(), dist.end()) - dist.begin();
        findLongestPath(from, longest_path, adj, dist);
        auto it = max_element(dist.begin(), dist.end());
        if (*it > 0)
        {
            vector<int> longest_path2;
            findLongestPath(it - dist.begin(), longest_path2, adj, dist);
            std::reverse(longest_path2.begin(), longest_path2.end());
            if (longest_path2[0] == 0)
                longest_path.insert(longest_path.end(), longest_path2.begin() + 1, longest_path2.end());
        }

        //根节点在最长路径上
        int max_height = longest_path.size() - 1;
        if (longest_path.size() % 2)
        {
            ans.push_back(longest_path[longest_path.size() / 2]);
        }
        else
        {
            int index = longest_path.size() / 2;

            ans.push_back(longest_path[longest_path.size() / 2]);
            ans.push_back(longest_path[longest_path.size() / 2 - 1]);

            // ans.push_back(longest_path[longest_path.size() / 2]);
            // ans.push_back(longest_path[longest_path.size() / 2 - 1]);
        }

        return ans;
    }
};

// int main()
// {
//     int n = 4;
//     vector<vector<int>> edges = {
//         {1, 0}, {1, 2}, {1, 3}};
//     Solution().findMinHeightTrees(n, edges);
//     return 0;
// }

// @lc code=end
